package top.metaspace.algorithm.sort.fast.sort;

import top.metaspace.algorithm.sort.Sort;

/**
 * @author panjun
 * @date 2018/7/1.
 * 快速排序
 */
public class FastSort implements Sort {
	public static void main(String[] args){

		int[] arr = {72,6,57,88,60,42,83,73,48,85};

		Sort sort = new FastSort();
		sort.sort(arr);
		sort.print(arr);


	}

	@Override
	public void sort(int[] arr) {
		fastSort(arr,0,arr.length-1);

	}


	public void fastSort(int[] arr,int left,int right){
		if(left<right) {
			int p = partition(arr, left, arr.length - 1);
			fastSort(arr, left, p - 1);
			fastSort(arr, p + 1, right);
		}

	}

	public int partition(int[] arr,int left,int right){

		int i=left;
		int j=right;
		int x = arr[left];

		while (i<j){
			while (i<j&&arr[j]>=x){
         j--;
			}
			if(i<j){
				arr[i]=arr[j];
				i++;
			}

			while (i<j&&arr[i]<=x){
				i++;
			}
			if(i<j){
				arr[j]=arr[i];
				j--;
			}
		}

		arr[i]=x;
		return i;


	}





}
